package org.example.myleet.p815;

import java.util.*;

/**
 * 广度优先搜索
 * 先将车站所在的线路收集，再按照车站传导开到各条线路
 */
public class Solution {
    public int numBusesToDestination(int[][] routes, int source, int target) {
        if (source == target) {
            return 0;
        }
        Map<Integer, Set<Integer>> stationRouteMap = new HashMap<>();
        for (int i = 0; i < routes.length; ++i) {
            int[] route = routes[i];
            for (int station : route) {
                Set<Integer> stationRoutes = stationRouteMap.getOrDefault(station, new HashSet<>());
                stationRoutes.add(i);
                stationRouteMap.put(station, stationRoutes);
            }
        }
        int routeCount = 1;
        Set<Integer> visitedRoutes = new HashSet<>(500);
        Deque<Integer> routeStack = new LinkedList<>();
        Set<Integer> startRoutes = stationRouteMap.getOrDefault(source, null);
        if (null == startRoutes) {
            return -1;
        }
        for (Integer route : startRoutes) {
            routeStack.push(route);
        }
        while (!routeStack.isEmpty()) {
            Set<Integer> nextRoutes = new HashSet<>();
            while (!routeStack.isEmpty()) {
                Integer route = routeStack.pop();
                if (isReach(routes[route], target)) {
                    return routeCount;
                }
                visitedRoutes.add(route);
                for (int station : routes[route]) {
                    Set<Integer> stationRoutes = stationRouteMap.getOrDefault(station, null);
                    if (null == stationRoutes) {
                        continue;
                    }
                    for (Integer stationRoute : stationRoutes) {
                        if (visitedRoutes.contains(stationRoute)) {
                            continue;
                        }
                        nextRoutes.add(stationRoute);
                    }
                }
            }
            for (Integer nextStation : nextRoutes) {
                routeStack.push(nextStation);
            }
            ++routeCount;
        }
        return -1;
    }

    private boolean isReach(int[] route, int target) {
        for (int station : route) {
            if (target == station) {
                return true;
            }
        }
        return false;
    }
}
